// 查找最大和连续子数组，并返回 和 与 这个子数组

// 方法	时间复杂度	空间复杂度	适用场景
// Kadane算法（推荐）	O(n)	O(1)	最优解

function maxSubArray(nums) {
  let maxSum = currentSum = nums[0];
  let start = end = 0;
  let tempStart = 0;

  for (let i = 1; i < nums.length; i++) {
    // 情况1：当前元素单独作为子数组更优（当前和为负数时）
    if (nums[i] > currentSum + nums[i]) {
      currentSum = nums[i];  // 重置当前和为当前元素
      tempStart = i;         // 临时起始索引更新为当前位置
    } 
    // 情况2：累加当前元素更优（当前和为正数时）
    else {
      currentSum = currentSum + nums[i];  // 当前和累加当前元素
    }

    // 更新最大和及子数组索引
    if (currentSum > maxSum) {
      maxSum = currentSum;    // 更新最大和
      start = tempStart;      // 最大子数组起始索引为临时记录的起始位置
      end = i;                // 最大子数组结束索引为当前位置
    }
  }

  return (
    maxSum,
    nums.slice(start, end + 1)
  )
}